import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/21 10:28
 * @description 回溯 + 记忆化搜索, 与 51题的区别，更简单，因为不需要画出所有解，只需要解的数量，那么不需要获取皇后位置
 */
public class Solution {
    public static void main(String[] args) {

    }
    private int sum = 0;
    public int totalNQueens(int n ) {
        // 同一列上不能有皇后，col统计
        Set<Integer> col = new HashSet<>();
        // 同一正斜线（左上到右下）不能有皇后
        Set<Integer> pos = new HashSet<>();
        // 同一反斜线（左下到右上）不能有皇后
        Set<Integer> neg = new HashSet<>();
        dfs(n, 0, col, pos, neg);
        return sum;
    }
    public void dfs(int n, int k, Set<Integer> col, Set<Integer> pos,
                    Set<Integer> neg) {
        if (k == n) {
            sum++;
            return;
        }else {
            // k 代表当前行，i代表当前列
            for(int i = 0; i < n; i++) {
                if (col.contains(i)) {
                    continue;
                }
                // 正斜线上行和列的差值相同
                int pos1 = k - i;
                if (pos.contains(pos1)) {
                    continue;
                }
                // 反斜线上行和列和相同
                int neg1 = k + i;
                if (neg.contains(neg1)) {
                    continue;
                }
                // 三种条件都满足，可以放置皇后
                col.add(i);
                pos.add(pos1);
                neg.add(neg1);
                dfs(n, k + 1, col, pos, neg);
                // 如果发现后面无法构成
                col.remove(i);
                pos.remove(pos1);
                neg.remove(neg1);
            }
        }
    }
}
